O(2^n)から計算量を減らす問題

O(2^n)から計算量を減らす問題 - けんちょんの競プロ精進記録

• DP

  • 現在の選択が遠い未来にまで直接的には影響を及ぼさない
    • 予めn個のモノをソート
  • ナップサック問題
  • 重み付き区間スケジューリング問題

• 連立1次方程式

  • https://archive.org/search.php?query=http%3A%2F%2Ftopcoder.g.hatena.ne.jp%2Fpepsin-amylase%2F20131203
  • ライツアウト系

• 最小カット

• 最大独立集合問題

  • フローに帰着するパターン
    • 二部グラフ上の最大独立集合問題
      • 頂点数 - 二部グラフの最大マッチング
    • 推移率を満たすDAG上の最大独立集合問題
      • Dilworthの定理により「DAG最小パス被覆」に等しい
    • 区間グラフ上の最大独立集合問題
      • 区間スケジューリング
  • パス上の最大独立集合問題
  • ツリー上の最大独立集合問題
  • 推移閉包を取った有向ツリー上の最大独立集合問題

• 貪欲法

  • 区間スケジューリング問題
  • マトロイド

• 最短路問題

• 最小カット問題

• マトロイド交差問題

  • 2つのマトロイド(E, F1), (E, F2)があったとき、$F1\cap F2$での最大化
    • 二部グラフの最大マッチング問題
    • 有向全域木問題
    • カラフル全域木問題
    • 全域木をパッキングする問題

• 指数時間アルゴリズム入門